home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / a_utils / lgrammar / src / function.c < prev    next >
C/C++ Source or Header  |  1993-09-09  |  17KB  |  690 lines
  1. /*************************************************************************/
  2. /*
  3.  *
  4.  * Filename: functions.c
  5.  *
  6.  */
  7.  
  8. #include "grammar.h"
  9.  
  10. #include <malloc.h>
  11. #include <math.h>
  12. #include <stdio.h>
  13. #include <sys/types.h>
  14. #include <sys/time.h>
  15. #include <sys/timeb.h>
  16.  
  17. #include <X11/Intrinsic.h>
  18.  
  19.  
  20. /* functions in functions.c:
  21.  *
  22.  * REGELN  *create_rule();
  23.  * SYMBOLE *create_node();
  24.  * REGELN  *init_grammar();
  25.  * int      count_char_word();
  26.  * char    *word_to_string();
  27.  * int      test_dimens();
  28.  * int      listlength();
  29.  * SYMBOLE *delete_wordlist();
  30.  * REGELN  *delete_grammarlist();
  31.  * int      klammerung();
  32.  * int      test_wk();
  33.  * double   random_number();
  34.  *
  35.  */
  36.  
  37.  
  38. /*************************************************************************/
  39. /* Function Name: create_rule
  40.  * Description: legt neuen Knoten vom Typ REGELN an
  41.  * Returns: Pointer auf den neuen Knoten
  42.  */
  43.  
  44. REGELN *create_rule()
  45. {
  46.   REGELN *p;
  47.  
  48.   p = (REGELN *)malloc(sizeof(REGELN));
  49.   if (p == NULL) 
  50.   {
  51.     fprintf(stderr, "Kein Speicher mehr frei!\n");
  52.     fprintf(stderr, "malloc-Aufruf in create_rule\n");
  53.     exit(1);
  54.   }
  55.  
  56.   /* Belegung mit Default-Werten */
  57.   p->symb   = ' ';
  58.   p->zusatz = 1;
  59.   p->indice = ' ';
  60.   p->list   = NULL;
  61.   p->next   = NULL;
  62.   return p;
  63. }
  64.  
  65. /*************************************************************************/
  66. /* Function Name: create_node
  67.  * Description: legt neuen Knoten vom Typ SYMBOLE an
  68.  * Returns: Pointer auf den neuen Knoten
  69.  */
  70.  
  71. SYMBOLE *create_node()
  72. {
  73.   SYMBOLE *p;
  74.  
  75.   p = (SYMBOLE *)malloc(sizeof(SYMBOLE));
  76.   if (p == NULL)
  77.   {
  78.     fprintf(stderr, "Kein Speicher mehr frei\n");
  79.     fprintf(stderr, "malloc-Aufruf in create_node\n");
  80.     exit(1);
  81.   }
  82.  
  83.   /* Belegung mit Default-Werten */
  84.   p->symb   = ' ';
  85.   p->zusatz = 1;
  86.   p->indice = ' ';
  87.   p->next   = NULL;
  88.   return p;
  89. }
  90.  
  91. /************************************************************************/
  92. /* Function Name: init_grammar
  93.  * Description: legt eine Regelliste aus den in einem String 
  94.  *              enthaltenen Zeichen an
  95.  * Arguments: str - String, der die Zeichen fuer die Regeln enthaelt
  96.  * Returns: Pointer auf Regelliste
  97.  */
  98.  
  99. REGELN *init_grammar(str)
  100. String str;
  101. {
  102.   REGELN *create_rule();
  103.   SYMBOLE *create_node();
  104.  
  105.   REGELN *p,
  106.          *pneu,
  107.          *p_end;
  108.  
  109.   SYMBOLE *qneu,
  110.           *q_end;
  111.  
  112.   char c;
  113.   int i = 0;
  114.  
  115.   int j;            /* laeuft durch Zusatz */
  116.   char czusatz[10]; /* Zusatz als einzelne char's */
  117.   double dzusatz;   /* Zusatz als double */
  118.  
  119.   p = create_rule();     /* Grammatik */
  120.   p_end = p;             /* Hilfszeiger setzen */
  121.  
  122.   qneu = create_node();  /* 1. Zeichen von Axiom */
  123.   p_end->list = qneu;
  124.   q_end = qneu; 
  125.   qneu->symb = str[i++];
  126.  
  127.   /* falls '<' nach gelesenem Zeichen angegeben */
  128.   while (str[i] == '<')
  129.   {
  130.     i++;
  131.     if (isdigit(str[i]))
  132.     {
  133.       j = 0;
  134.       while ((c = str[i]) != '>')
  135.       {
  136.         /* solange nicht '>' */
  137.         i++;
  138.         czusatz[j++] = c;
  139.       }
  140.       czusatz[j] = NULL;
  141.       dzusatz = atof(czusatz);
  142.       qneu->zusatz = dzusatz;
  143.       i++;
  144.     }
  145.     else
  146.     {
  147.       if (isalpha(str[i]))
  148.       {
  149.         qneu->indice = str[i];
  150.         i += 2;
  151.       }
  152.     }
  153.   } /* Ende von '<>'-Bearbeitung */
  154.  
  155.   while (((c = str[i]) != '\n') && (c != '\0')) /* Axiom nicht beendet */
  156.   {
  157.     qneu = create_node();
  158.     q_end->next = qneu;
  159.     q_end = qneu;
  160.     qneu->symb = c;
  161.     i++;
  162.  
  163.     /* falls '<' nach gelesenem Zeichen angegeben */
  164.     while (str[i] == '<')
  165.     {
  166.       i++;
  167.       if (isdigit(str[i]))
  168.       {
  169.         j = 0;
  170.         while ((c = str[i]) != '>')
  171.         {
  172.           /* solange nicht '>' */
  173.           i++;
  174.           czusatz[j++] = c;
  175.         }
  176.         czusatz[j] = NULL;
  177.         dzusatz = atof(czusatz);
  178.         qneu->zusatz = dzusatz;
  179.         i++;
  180.       }
  181.       else
  182.       {
  183.         if (isalpha(str[i]))
  184.         {
  185.           qneu->indice = str[i];
  186.           i += 2;
  187.         }
  188.       }
  189.     } /* Ende von '<>'-Bearbeitung */
  190.   }
  191.  
  192.   while((c = str[i++]) != '\0')  /* String noch nicht abgearbeitet */
  193.   {  
  194.     switch(c)
  195.     {
  196.     case '\n':  /* neue Produktion beginnt */
  197.                switch(str[i]) /* naechstes Symbol */
  198.                {
  199.                case '\0': /* Stringende */
  200.                           break;
  201.  
  202.                case '\n': /* leere Produktion */
  203.                           break;
  204.  
  205.                default: /* str[i] ist 1.Symbol von neuer Produktion */
  206.                    pneu = create_rule();     /* neuer Regelknoten */
  207.                    p_end->next = pneu;       /* Knoten anhaengen */ 
  208.                    p_end = pneu;
  209.                    pneu->symb = str[i++];      /* zugehoerige Werte */
  210.  
  211.                    /* falls '<' nach gelesenem Zeichen angegeben */
  212.                    while (str[i] == '<')
  213.                    {
  214.                      i++;
  215.                      if (isdigit(str[i]))
  216.                      {
  217.                        j = 0;
  218.                        while ((c = str[i++]) != '>')
  219.                        {
  220.                          /* solange nicht '>' */
  221.                          czusatz[j++] = c;
  222.                        }
  223.                        czusatz[j] = NULL;
  224.                        dzusatz = atof(czusatz);
  225.                        pneu->zusatz = dzusatz;
  226.                      }
  227.                      else
  228.                      {
  229.                        if (isalpha(str[i]))
  230.                        {
  231.                          pneu->indice = str[i];
  232.                          i += 2;
  233.                        }
  234.                      }
  235.                    } /* Ende von '<>'-Bearbeitung */
  236.  
  237.                    while (str[i] == ' ') i++;   /* Blanks ueberlesen */
  238.  
  239.                    if (str[i] == '=')
  240.                    {
  241.                      /* Ableitungszeichen */
  242.                      i++;
  243.  
  244.                      if (str[i] == '<')
  245.                      {
  246.                        /* Wahrscheinlichkeitsangabe fuer Regel */
  247.                        i++;
  248.                        j = 0;
  249.                        while ((c = str[i++]) != '>')
  250.                        {
  251.                          /* solange nicht '>' */
  252.                          czusatz[j++] = c;
  253.                        }
  254.                        czusatz[j] = NULL;
  255.                        dzusatz = atof(czusatz);
  256.                        pneu->zusatz = dzusatz;
  257.                      }
  258.  
  259.                      while (str[i] == ' ') i++; /* Blanks ueberlesen */
  260.  
  261.                      qneu = create_node();    /* neuer Symbolknoten */
  262.                      p_end->list = qneu;      /* Knoten anhaengen */
  263.                      q_end = qneu;
  264.                      qneu->symb = str[i++];    /* zugehoerige Werte */
  265.  
  266.                      /* falls '<' nach gelesenem Zeichen angegeben */
  267.                      while (str[i] == '<')
  268.                      {
  269.                        i++;
  270.                        if (isdigit(str[i]))
  271.                        {
  272.                          j = 0;
  273.                          while ((c = str[i++]) != '>')
  274.                          {
  275.                            /* solange nicht '>' */
  276.                            czusatz[j++] = c;
  277.                          }
  278.                          czusatz[j] = NULL;
  279.                          dzusatz = atof(czusatz);
  280.                          qneu->zusatz = dzusatz;
  281.                        }
  282.                        else
  283.                        {
  284.                          if (isalpha(str[i]))
  285.                          {
  286.                            qneu->indice = str[i];
  287.                            i += 2;
  288.                          }
  289.                        }
  290.                      } /* Ende von '<>'-Bearbeitung */
  291.                    }
  292.                    else
  293.                    {
  294.                      /* ungueltige Produktion, da '=' fehlt */
  295.                      p = NULL; /* damit wird Grammatik ungueltig */
  296.                      return p;
  297.                    }
  298.                  }
  299.                  break;
  300.  
  301.     default: /* neues Symbol */
  302.         qneu = create_node();  /* neuer Symbolknoten */ 
  303.         q_end->next = qneu;    /* Knoten an Liste anhaengen */
  304.         q_end = qneu;
  305.         qneu->symb = c;        /* zugehoerige Werte */
  306.  
  307.         /* falls '<' nach gelesenem Zeichen angegeben */
  308.         while (str[i] == '<')
  309.         {
  310.           i++;
  311.           if (isdigit(str[i]))
  312.           {
  313.             j = 0;
  314.             while ((c = str[i++]) != '>')
  315.             {
  316.               /* solange nicht '>' */
  317.               czusatz[j++] = c;
  318.             }
  319.             czusatz[j] = NULL;
  320.             dzusatz = atof(czusatz);
  321.             qneu->zusatz = dzusatz;
  322.           }
  323.           else
  324.           {
  325.             if (isalpha(str[i]))
  326.             {
  327.               qneu->indice = str[i];
  328.               i += 2;
  329.             }
  330.           }
  331.         } /* Ende von '<>'-Bearbeitung */
  332.         break;
  333.  
  334.     } /* switch */
  335.   } /* while */
  336.   return p;
  337. }
  338.  
  339. /*************************************************************************/
  340. /* Function Name: count_char_word
  341.  * Description: bestimmt die Wortlaenge von symbollist
  342.  * Arguments: symbollist - Zeiger auf eine verkettete Liste mit Elementen
  343.  *                         vom Typ SYMBOLE
  344.  * Returns: laenge - Anzahl der char von symbollist
  345.  */
  346.  
  347. int count_char_word(symbollist)
  348. SYMBOLE *symbollist;
  349. {
  350.   SYMBOLE *hilfe;
  351.   int laenge = 0;
  352.  
  353.   hilfe = symbollist;
  354.   while (hilfe)
  355.   {
  356.     laenge ++;
  357.     hilfe = hilfe->next;
  358.   }
  359.   return laenge;
  360. }
  361.  
  362. /*************************************************************************/
  363. /* Function Name: word_to_string
  364.  * Description: kopiert die Symbole von list in einen char-String, wobei
  365.  *              das Ableitungsende (deriv_end) bei einer symbolweisen
  366.  *              Ableitung durch ein Blank im String gekennzeichnet wird
  367.  * Arguments: wordlist  - Zeiger auf eine Liste von SYMBOLE
  368.  *            deriv_end - Zeiger auf das Ableitungsende
  369.  *                        (innerhalb von list)
  370.  * Returns: zeichen - char-String
  371.  */
  372.  
  373. char *word_to_string(wordlist, deriv_end)
  374. SYMBOLE *wordlist,
  375.         *deriv_end;
  376. {
  377.   int count_char_word();
  378.  
  379.   SYMBOLE *hilfe;
  380.   char *zeichen;
  381.   int i;
  382.  
  383.   i = count_char_word(wordlist);
  384.  
  385.   zeichen = (char *)malloc(sizeof(char)*(6*i));
  386.   if (zeichen == NULL)
  387.   {
  388.     fprintf(stderr, "Kein Speicher mehr frei!\n");
  389.     fprintf(stderr, "malloc-Aufruf in word_to_string\n");
  390.     exit(1);
  391.   }
  392.  
  393.   i = 0;
  394.   hilfe = wordlist;
  395.   while (hilfe)
  396.   {
  397.     /* markiert das Ende der Teilableitung */
  398.     if ((deriv_end != wordlist) && (hilfe == deriv_end))
  399.     {
  400.       zeichen[i++] = ' ';
  401.     }
  402.  
  403.     zeichen[i++] = hilfe->symb;
  404.  
  405.     /* falls Indice vorhanden */
  406.     if (hilfe->indice != ' ')
  407.     {
  408.       zeichen[i++] = '<';
  409.       zeichen[i++] = hilfe->indice;
  410.       zeichen[i++] = '>';
  411.     }
  412.  
  413.     /* falls Zusatz ungleich 1 vorhanden */
  414.     if (hilfe->zusatz != 1)
  415.     {
  416.       zeichen[i++] = '<';
  417.       zeichen[i++] = '>';
  418.     }
  419.     hilfe = hilfe->next; 
  420.   }
  421.  
  422.   zeichen[i] = NULL;
  423.  
  424.   return zeichen;
  425. }
  426.  
  427. /*************************************************************************/
  428. /* Function Name: test_dimens
  429.  * Description: Test, ob in der eingelesenen Grammatik nur 2D- oder
  430.  *              auch 3D-Symbole enthalten sind
  431.  * Arguments: str_eingabe - enthaelt die Symbole
  432.  * Returns: dimens - 2: nur 2D-Symbole
  433.  *                   3: auch 3D-Symbole
  434.  */
  435.  
  436. int test_dimens(eingabe)
  437. String eingabe;
  438. {
  439.   String d3_symbole = "^&\/${}G,~!%";
  440.   int eingabe_laenge;
  441.   int dimens;
  442.  
  443.   eingabe_laenge = strlen(eingabe);
  444.   if (strcspn(eingabe, d3_symbole) != eingabe_laenge)
  445.   {
  446.     dimens = 3;
  447.   }
  448.   else
  449.   {
  450.     dimens = 2;
  451.   }
  452.  
  453.   return dimens;
  454. }
  455.  
  456. /*************************************************************************/
  457. /* Function Name: listlength
  458.  * Description: analog zu strlen wird die Laenge einer Liste bestimmt,
  459.  *              d.h. es werden die Elemente vom Typ SYMBOLE gezaehlt
  460.  * Arguments: list - Pointer auf die Liste
  461.  * Returns: length - Laenge von list
  462.  */
  463.  
  464. int listlength(list)
  465. SYMBOLE *list;
  466. {
  467.   int length = 0;
  468.   SYMBOLE *help = list;
  469.  
  470.   while (help)
  471.   {
  472.     length ++;
  473.     help = help->next;
  474.   }
  475.   return length;
  476. }
  477.  
  478. /*************************************************************************/
  479. /* Function Name: delete_wordlist
  480.  * Description: gesamte list wird geloescht, slist ist anschl. NULL 
  481.  * Arguments: slist - Zeiger auf eine verkettete Liste mit Elementen
  482.  *                    vom Typ SYMBOLE
  483.  * Returns: slist
  484.  */
  485.  
  486. SYMBOLE *delete_wordlist(slist)
  487. SYMBOLE *slist;
  488. {
  489.   SYMBOLE *help;
  490.  
  491.   help = slist;
  492.   slist = slist->next;
  493.  
  494.   while (slist)
  495.   {
  496.     free(help);
  497.     help = slist;
  498.     slist = slist->next;
  499.   }
  500.   free(help);
  501.   slist = NULL;
  502.  
  503.   return slist;
  504. }
  505.  
  506. /*************************************************************************/
  507. /* Function Name: delete_grammarlist
  508.  * Description: gesamte list wird geloescht, rlist ist anschl. NULL 
  509.  * Arguments: rlist - Zeiger auf eine verkettete Liste mit Elementen
  510.  *                    vom Typ REGELN, wobei jeder Knoten auf eine
  511.  *                    Liste mit Elementen vom Typ SYMBOLE zeigen kann
  512.  * Returns: rlist
  513.  */
  514.  
  515. REGELN *delete_grammarlist(rlist)
  516. REGELN *rlist;
  517. {
  518.   SYMBOLE *delete_wordlist();
  519.  
  520.   REGELN *help;
  521.  
  522.   help = rlist;
  523.   rlist = rlist->next;
  524.  
  525.   while (rlist)
  526.   {
  527.     if (help->list)
  528.     {
  529.       /* rechte Seite der Produktion loeschen */
  530.       help->list = delete_wordlist(help->list);
  531.     }
  532.     /* linke Seite der Produktion loeschen */
  533.     free(help);
  534.     help = rlist;
  535.     rlist = rlist->next;
  536.   }
  537.  
  538.   if (help->list)
  539.   {
  540.     help->list = delete_wordlist(help->list);
  541.   }
  542.   free(help);
  543.   rlist = NULL;
  544.   return rlist;
  545. }
  546.  
  547. /*************************************************************************/
  548. /* Function Name: klammerung
  549.  * Description: ueberprueft, ob in rlist die Klammern '[' und ']' bzw.
  550.  *              '{' und '}' richtig gesetzt wurden. Die Ueberpruefung
  551.  *              wird produktionsweise durchgefuehrt.
  552.  * Arguments: rlist - Zeiger auf eine verkettete Liste mit Elementen
  553.  *                    vom Typ REGELN, wobei jeder Knoten auf eine
  554.  *                    Liste mit Elementen vom Typ SYMBOLE zeigt
  555.  * Returns: fehler - 0: kein Fehler
  556.  *                   1: Fehler bei Klammersetzung
  557.  */
  558.  
  559. int klammerung(rlist)
  560. REGELN *rlist;
  561. {
  562.   REGELN *philfe;
  563.   SYMBOLE *qhilfe;
  564.  
  565.   int i=0,  /* zaehlt die gefundenen [ bzw. ] Klammern */ 
  566.       j=0;  /* zaehlt die gefundenen { bzw. } Klammern */
  567.   int fehler=0; /* merkt sich aufgetretenen Fehler bei Klammersetzung */
  568.  
  569.   philfe = rlist;
  570.   while (philfe)
  571.   {
  572.     qhilfe = philfe->list;
  573.     while (qhilfe)
  574.     {
  575.        switch(qhilfe->symb)
  576.        {
  577.        case '[': i++;   /* neue oeffnende Klammer */
  578.                  break;
  579.  
  580.        case ']': i--;   /* neue schliessende Klammer */
  581.                  if (i<0) fehler = 1;
  582.                  break;
  583.  
  584.        case '{': j++;   /* neue oeffnende Klammer */
  585.                  if (j>1) fehler = 1;
  586.                  break;
  587.  
  588.        case '}': j--;   /* neue schliessende Klammer */
  589.                  if (j<0) fehler = 1;
  590.                  break;
  591.        }
  592.        qhilfe = qhilfe->next;
  593.     }
  594.     if ((i!=0)||(j!=0)) fehler = 1;
  595.     philfe = philfe->next;  /* naechste Produktion wird ueberprueft */
  596.     i=j=0;
  597.   }
  598.  
  599.   return fehler;
  600. }
  601.  
  602. /*************************************************************************/
  603. /* Function Name: test_wk
  604.  * Description: ueberprueft, ob die Summe der angegebenen Wahrscheinlich-
  605.  *              keiten bei den Produktionsregeln fuer gleiche Zeichen
  606.  *              gleich 1 ist.
  607.  * Arguments: rlist
  608.  * Returns: fehler - 0: kein Fehler
  609.  *                  20: Fehler
  610.  */
  611.  
  612. int test_wk(rlist)
  613. REGELN *rlist;
  614. {
  615.   REGELN *philfe,
  616.          *prod;
  617.  
  618.   double sum_wk = 0;
  619.   int fehler = 0;
  620.  
  621.   philfe = rlist;
  622.   while (philfe)
  623.   {
  624.     if (philfe->zusatz != 1) /* oder in der Naehe ?? */
  625.     {
  626.       prod = rlist;
  627.       while (prod)
  628.       {
  629.         if ( (prod->symb == philfe->symb) &&
  630.              (prod->indice == philfe->indice) )
  631.         {
  632.           sum_wk += prod->zusatz;
  633.         }
  634.         prod = prod->next;
  635.       }
  636.       if (sum_wk != 1.0)
  637.       {
  638.         fehler = 20;
  639.         return fehler;
  640.       }
  641.     }
  642.     philfe = philfe->next;
  643.     sum_wk = 0;
  644.   }
  645.  
  646.   return fehler;
  647. }
  648.  
  649. /*************************************************************************/
  650. /* Function Name: random_number
  651.  * Description: liefert eine Zufallszahl zwischen 0 und 1
  652.  * Returns: number - Zufallszahl
  653.  */
  654. double random_number()
  655. {
  656.   static int i = 0;
  657.  
  658.   double number;
  659.   int tt;
  660.   struct timeb tp;
  661.  
  662.   if (i==0)
  663.   {
  664.     ftime(&tp);
  665.     tt = tp.millitm;
  666.     number = (double)srand(tt) / 10000;
  667.     number += (-(int)number);
  668.     i++;
  669.   }
  670.   else
  671.   {
  672.     number = rand();
  673.     number /= 10000;
  674.     number += (-(int)number);
  675.   }
  676.   return number;
  677. }
  678.  
  679. /*************************************************************************/
  680. /* Function Name: 
  681.  * Description: 
  682.  * Arguments: 
  683.  * Globals: 
  684.  * Returns: 
  685.  */
  686.  
  687.  
  688. /************************************************************************/
  689. /************************************************************************/
  690.